import {scan} from './LexParser'

//构建语法树
let syntax = {
  Program: [["StatementList"]],
  StatementList: [
    ["Statement"],
    ["StatementList","Statement"]
  ],
  Statement: [
    ["ExpressionStatement"],
    ["IfStatement"],
    ["VariableDeclaration"],
    ["FunctionDeclaration"]
  ],
  IfStatement: [
    ["if", "(","Expression",")","Statement"]
  ],
  VariableDeclaration:[
    ["var", "Identifier"]
  ],
  FunctionDeclaration:[
    ["function", "Identifier", "(",")","{","StatementList","}"]
  ],
  ExpressionStatement:[
    ["Expression",";"],
  ],
  Expression:[
    ["AdditiveExpression"],
  ],
  AdditiveExpression: [
    ["MultiplicativeExpression"],
    ["AdditiveExpression", "+" , "MultiplicativeExpression"],
    ["AdditiveExpression", "-" , "MultiplicativeExpression"],
  ],
  MultiplicativeExpression: [
    ["PrimaryExpression"],
    ["MultiplicativeExpression","*", "PrimaryExpression"],
    ["MultiplicativeExpression","/","PrimaryExpression"],
  ],
  PrimaryExpression:[
    ["(", "Expression", ")"],
    ["Literal"],
    ["Identifier"]
  ],
  Literal: [
    ["Number"]
  ]
}

//使用hash去去除重复节点
let hash = {

}

/**
 * 广度优先搜索获取token
 */
function closure(state){
  hash[JSON.stringify(state)] = state
  //广度优先搜索
  let queue = []
  for(let symbol in state){
    queue.push(symbol);
  }
  while(queue.length){
    let symbol = queue.shift();
    console.log(symbol);
    if(syntax[symbol]){
      for(let rule of syntax[symbol]){
        if(!state[rule[0]]){
          queue.push(rule[0])
        }
        // state[rule[0]] = true

        let current = state;
        for(let part of rule){
          if(!current[part]){
            current[part] = {}
          }
          current = current[part]
        }
        // current.$isRuleEnd = true
        current.$reduceType = symbol
        current.$reduceLenth = rule.length
      }
    }
  }

  for(let symbol in state){
    if(symbol.match(/^$/)){
      return
    }
    if(hash[JSON.stringify(state[symbol])]){
      state[symbol] = hash[JSON.stringify(state[symbol])]
    } 
    else 
      closure(state[symbol])
  }
}

let end = {
  $isEnd: true
}

let start = {
  "Program": end
}



closure(start)

let source = `
  var a;
`

function parse(source){
  
  let stack = [start]
  function reduce(){
    let state = stack[stack.length -1];
    if(state.$reduceType) {
      let children = []
      for (let i; i< state.$reduceLenth; i++){
        children.push(stack.pop());
        //create non-terminal symbol and shift it

        shift({
          type: state.$reduceType,
          children: children.reverse()
        })
      }
    }
  }

  function shift(symbol){
    let state = stack[stack.length -1];
    if(symbol.type in state){
      stack.push(symbol);
    } else {
      /*reduce to non-terminal symbols */
      reduce();
      shift(symbol)
    }
  }

  for(let symbol/*terminal symbols */ of scan(source)) {
    shift(symbol);
  }
}

parse(source)